package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.LinkedProblem;

/**
 * 要求 On时间 O1空间
 * <p>
 * 完整翻转不行, 翻转后半段, 有点bug, 2里修复
 *
 * @author tzp
 * @since 2020/10/15
 */
public class LC234_1 implements LinkedProblem {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        //求长度
        int size = 0;
        ListNode tmp = head;
        while (tmp.next != null) {
            tmp = tmp.next;
            size++;
        }
        size++;
        int rightStart = (size + 1) / 2;
        //翻转后半段
        ListNode rightHead = tmp;//最后一个
        ListNode pre = tmp;
        tmp = head;
        for (int i = 0; i < size - 1; i++) {
            if (i >= rightStart) {
                pre.next = tmp;
                pre = pre.next;
            }

            if (i == rightStart - 1) {
                ListNode x = tmp;
                tmp = tmp.next;
                x.next = null;
            } else {
                tmp = tmp.next;
            }
        }
        pre.next = null;
        System.out.println(head);
        System.out.println(rightHead);
        while (rightHead != null) {
            if (rightHead.val != head.val) return false;
            rightHead = rightHead.next;
            head = head.next;
        }
        return true;
    }


    public static void main(String[] args) {
        ListNode a = ListNode.arrayToListNode(new int[]{1, 3, 2, 4, 3, 2, 1});
        System.out.println(new LC234_1().isPalindrome(a));
    }
}
